// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-08 12:39
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

public class PlatesBetweenCandlesPrefix {
    /**
     * 前缀和实例
     */
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length(), m = queries.length;
        int sum = 0;
        // 用于存储前缀和，当前面没有蜡烛的时候前缀和为-1
        int[] prefixSum = new int[n];
        int[] ans = new int[m];
        for (int i = 0; i < n; i++) {
            // 数据预处理 -> 前缀和数组创建
            if (s.charAt(i) == '*') {
                sum++;
            }
            prefixSum[i] = sum;
        }
        // 定位‘|’的前一个位置 -> 定位右边界使用left; 定位左边界使用right
        int[] left = new int[n];
        int[] right = new int[n];
        // 使用-1表示当前位置没有左边界或者没有右边界
        for (int i = 0, k = -1; i < n; i++) {
            if (s.charAt(i) == '|') {
                // 检测到左边界出现
                k = i;
            }
            left[i] = k;
        }
        // 确定左边界
        for (int i = n - 1, r = -1; i >= 0; i--) {
            if (s.charAt(i) == '|') {
                r = i;
            }
            right[i] = r;
        }
        for (int i = 0; i < m; i++) {
            int x = right[queries[i][0]], y = left[queries[i][1]];
            ans[i] = x == -1 || y == -1 || x >= y ? 0 : prefixSum[y] - prefixSum[x];
        }
        return ans;
    }
}
